package TrieTree;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Set;

/*
回文对
给定一个由唯一字符串构成的 0 索引数组 words。
回文对 是一对整数 (i, j) ，满足以下条件：
0 <= i, j < words.length，
i != j ，并且
words[i] + words[j]（两个字符串的连接）是一个回文串。
返回一个数组，它包含words 中所有满足 回文对 条件的字符串。

你必须设计一个时间复杂度为 O(sum of words[i].length) 的算法。

示例 1：
输入：words = ["abcd","dcba","lls","s","sssll"]
输出：[[0,1],[1,0],[3,2],[2,4]]
解释：可拼接成的回文串为 ["dcbaabcd","abcddcba","slls","llssssll"]
示例 2：
输入：words = ["bat","tab","cat"]
输出：[[0,1],[1,0]]
解释：可拼接成的回文串为 ["battab","tabbat"]
示例 3：
输入：words = ["a",""]
输出：[[0,1],[1,0]]

作者：LeetCode
链接：https://leetcode.cn/leetbook/read/trie/x75mhj/
 */

public class _43回文对_纯脑残题_ {
    public static void main(String[] args) {

    }

    //GG
    class Solution {
        public List<List<Integer>> palindromePairs(String[] words) {
            Trie trie = new Trie();
            for (int i = 0; i < words.length; i++) {
                trie.insert(words[i],i);
            }
            List<List<Integer>> res = new ArrayList<>();
            for (int i = 0; i < words.length; i++) {
                if(words[i].equals("")){
                    for (int j = 0; j < words.length; j++) {
                        if (i == j) continue;
                        if (trie.isPalindrome(words[j])) {
                            List<Integer> list = new ArrayList<>();
                            list.add(i);
                            list.add(j);
                            res.add(list);
                            List<Integer> list2 = new ArrayList<>();
                            list2.add(j);
                            list2.add(i);
                            res.add(list2);
                        }
                    }
                    continue;
                }
                trie.search(words[i],res,i);
            }
            return res;
        }

        class Trie{
            HashMap<Character,Trie> children;
            int index;
            String word;
            public Trie(){
                this.children = new HashMap<Character,Trie>();
                this.index = -1;
                this.word = "";
            }

            public void insert(String word,int index){
                Trie cur = this;
                for (int i = 0; i < word.length(); i++) {
                    char ch = word.charAt(i);
                    if(!cur.children.containsKey(ch)){
                        cur.children.put(ch, new Trie());
                    }
                    cur = cur.children.get(ch);
                }
                cur.index = index;
            }

            public void search(String word, List<List<Integer>> res, int i){
                Trie cur = this;
                for (int n = word.length() - 1; n >= 0; n--) {
                    char ch = word.charAt(n);

                    if(!cur.children.containsKey(ch)){
                        return;
                    }
                    cur = cur.children.get(ch);
                    if(cur.index != -1 && !(word.equals(cur.word))){
                        boolean palindrome = isPalindrome(word.substring(0, n));
                        if(palindrome){
                            List<Integer> list = new ArrayList<>();
                            list.add(cur.index);
                            list.add(i);
                            res.add(list);
                        }
                    }
                    if(n == 0){
                        if (!cur.children.isEmpty()){
                            Set<Character> characters = cur.children.keySet();
                            for (Character character : characters) {
                                Trie temp = cur.children.get(character);
                                String substring = temp.word.substring(word.length());
                                boolean palindrome = temp.isPalindrome(substring);
                                if(palindrome){
                                }
                            }
                        }
                    }
                }
            }

            public boolean isPalindrome(String word){
                int i = 0, j = word.length() - 1;
                while (i < j) {
                    if (word.charAt(i) != word.charAt(j)) {
                        return false;
                    }
                    i++;
                    j--;
                }
                return true;
            }
        }
    }

    //前面的路以后再来探索吧  *
    //class Solution {
    //    private Trie preDict = new Trie();
    //    private Trie postDict = new Trie();
    //
    //    public List<List<Integer>> palindromePairs(String[] words) {
    //        for (int i = 0; i < words.length; i++) {
    //            preDict.insert(words[i], i);
    //            postDict.insert(new StringBuffer(words[i]).reverse().toString(), i);
    //        }
    //
    //        List<List<Integer>> ans = new ArrayList<>();
    //
    //        for (int i = 0; i < words.length; i++) {
    //            String word = words[i]; int n = word.length();
    //            boolean[][] isPalindrome = manacher(word);
    //
    //            Trie node; int j;
    //            for (node = postDict, j = 0; j < n; j++) {
    //                if (isPalindrome[1][j] && node.word != -1)
    //                    ans.add(Arrays.asList(i, node.word));
    //
    //                int k = word.charAt(j) - 'a';
    //                if (node.alpha[k] == null) break;
    //                node = node.alpha[k];
    //            }
    //            if (j == n && node.word > i) ans.add(Arrays.asList(i, node.word));
    //
    //            for (node = preDict, j = n - 1; j >= 0; j--) {
    //                if (isPalindrome[0][j] && node.word != -1)
    //                    ans.add(Arrays.asList(node.word, i));
    //
    //                int k = word.charAt(j) - 'a';
    //                if (node.alpha[k] == null) break;
    //                node = node.alpha[k];
    //            }
    //            if (j == -1 && node.word > i) ans.add(Arrays.asList(node.word, i));
    //        }
    //
    //        return ans;
    //    }
    //
    //    private boolean[][] manacher(String s) {
    //        int m = s.length(); boolean[][] check = new boolean[2][m];
    //        if (m == 0) return check;
    //        if (m == 1) { check[0][0] = true; check[1][0] = true; return check; }
    //
    //        StringBuffer buffer = new StringBuffer("#");
    //        for (int i = 0; i < m; i++) {
    //            buffer.append(s.charAt(i));
    //            buffer.append("#");
    //        }
    //
    //        String t = buffer.toString();
    //        int right = 0, n = t.length();
    //        int[] armLen = new int[n];
    //        for (int i = 1; i < n - 1; i++) {
    //            int jump = 1, p = right + armLen[right];
    //            if (p > i) jump += Math.min(p - i, armLen[2 * right - i]);
    //
    //            int l = i - jump, r = i + jump;
    //            while (l >= 0 && r < n && t.charAt(l) == t.charAt(r)) { l--; r++; }
    //
    //            armLen[i] = r - i - 1;
    //            if (r > ++p) right = i;
    //            if (l == -1) check[0][i - 1] = true;
    //            if (r == n) check[1][i - m] = true;
    //        }
    //        return check;
    //    }
    //}
    //
    //class Trie {
    //    private static final int LOWERCASE = 26;
    //    public int word;
    //    public Trie[] alpha;
    //
    //    public Trie() {
    //        word = -1; alpha = new Trie[LOWERCASE];
    //    }
    //
    //    public void insert(String word, int id) {
    //        Trie nav = this;
    //        for (int i = 0; i < word.length(); i++) {
    //            int j = word.charAt(i) - 'a';
    //            if (nav.alpha[j] == null) nav.alpha[j] = new Trie();
    //            nav = nav.alpha[j];
    //        }
    //        nav.word = id;
    //    }
    //}




}
